<?php
/**
 * @title 1546. 和为目标值的最大数目不重叠非空子数组数目 - 哈希+递归
 * @author start2004
 */

// ini_set("memory_limit", "128M");


class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function maxNonOverlapping($nums, $target) {
        /**
         * @since 2020-08-11 哈希数字
         */
        $hashs = [];
        foreach ($nums as $num){
            if(isset($hashs[$num])){
                $hashs[$num] += 1;
            } else {
                $hashs[$num] = 1;
            }
        }

        /**
         * @since 2020-08-11 结果集
         */
        $result = 0;

        /**
         * @since 2020-08-11 1个数
         */
        if(isset($hashs[$target])){
            $result += $hashs[$target];
            unset($hashs[$target]);
        } else {}



        /**
         * @since 2020-08-11 2个不同数
         */
        $exists = [];
        foreach ($hashs as $num1=>$count1){
            if(!isset($exists[$num1])){
                $num2 = $target-$num1;
                if(isset($hashs[$num2])){
                    $count2 = $hashs[$num2];

                    /**
                     * @since 2020-08-11 组合次数
                     */
                    $min = min($count1, $count2);
                    if($count1>$min){
                        $hashs[$num1] = $count1-$min;
                    } else {
                        unset($hashs[$num1]);
                    }
                    if($count2>$min){
                        $hashs[$num2] = $count2-$min;
                    } else {
                        unset($hashs[$num2]);
                    }

                    /**
                     * @since 2020-08-11 已使用
                     */
                    $exists[$num1] = 1;
                    $exists[$num2] = 1;
                } else {}
            } else {}
        }

        /**
         * @return
         */
        return $result;
    }
}


/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.11_4.php
 */
$datas = [
    [[1,1,1,1,1],2],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->maxNonOverlapping($data[0], $data[1]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
